package leetcode.code040;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 超时 124 / 175 个通过测试用例
 * @author Max
 * @date 2021年9月6日
 * @description
 */
public class Solution extends Solution040 {

	@Override
	public List<List<Integer>> combinationSum2(int[] candidates, int target) {
		Arrays.sort(candidates);
		return combinationSum(candidates, 0, target);
	}

	private List<List<Integer>> combinationSum(int[] candidates, int start, int target) {
		List<List<Integer>> result = new ArrayList<>();
		for (int i = start; i < candidates.length; i++) {
			int num = candidates[i];
			if (i > start && num == candidates[i - 1]) {
				continue;//重复不做
			}
			List<Integer> part1 = new ArrayList<>();
			part1.add(num);
			int cha = target - num;
			if (cha == 0) {
				result.add(new ArrayList<>(part1));
			} else {
				List<List<Integer>> part2s = this.combinationSum(candidates, i + 1, cha);
				for (List<Integer> part2 : part2s) {
					List<Integer> temp = new ArrayList<>();
					temp.addAll(part1);
					temp.addAll(part2);
					result.add(temp);
				}
			}
		}
		return result;
	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
	}

}
